/* 试编写算法将单链表就地逆置 */

#include <iostream>
#include "headfun.h"
using namespace std;

// 原地逆序，头插法
void reverse(LNode *&L)
{
  // 指向头节点的下一个结点
  LNode *p = L->next, *r;
  
  // 头节点的下一位，先置空
  L->next = NULL;
  
  // 遍历链表
  while (p != NULL)
  {
    // r为p的下一个结点
    r = p->next;
    
    // p的下一位指向L的下一位
    p->next = L->next;
    
    // L的下一位指向p
    L->next = p;
    
    // p移动到下一个结点
    p = r;
  }
}

// 原地逆序
void Reverse(LNode *&L)
{
  // 指向前3个结点
  LNode *p = L->next, *r = p->next;
  
  // 辅助
  LNode *pre;
  
  // 第二个结点指向空
  p->next = NULL;
  
  // 遍历链表，改变指向
  while (r != NULL)
  {
    pre = p;
    p = r;
    r = r->next;
    p->next = pre;
  }
  L->next = p;
}

int main()
{
  // 创建带头节点的链表
  LNode *L = head_Linklist();
  
  // 原地逆序
  Reverse(L);
  
  // 遍历链表，打印信息
  LNode *q = L->next;
  while (q != NULL)
  {
    cout << q->data << " ";
    q = q->next;
  }
  return 0;
}